class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        node = TreeNode(inorder[0])
        root_list = [node]
        index = 0
        for i in range(1, len(inorder)):
            next_node = TreeNode(inorder[i])
            if root_list[-1].val == postorder[index]:
                while root_list[-1].val == postorder[index]:
                    index += 1
                    node = root_list.pop()
                    if len(root_list) > 0:
                        root_list[-1].right = node
                    else:
                        break
                next_node.left = node
                root_list.append(next_node)
            else:
                root_list.append(next_node)
        for i in range(1, len(root_list)):
            root_list[i - 1].right = root_list[i]
        return root_list[0]

data = Solution()
inorder = [1, 2, 3]
postorder = [3, 2, 1]
print(data.buildTree(inorder, postorder))
